Standard application specific integrated circuit (ASIC) modules that perform fixed-point arithmetic functions on numbers having N bits require at least log N levels of logic, producing a delay proportional to log N. It is known that the delay can be reduced by using long number formats, but long number formats require additional hardware (gates). Consequently, the ASIC design is usually selected as a trade-off of the delay and module size.
One design technique for faster fixed-point arithmetic modules is to use a “double size” representation in place of a standard N-bit representation of N-bit number. Integers of the range 0 . . . 2N−1, or −2N−1 . . . 2N−1−1, are considered as pairs (A and B), where A and B each have N bits. Adders (and subtractors) can be implemented with a fixed delay that is not dependant on N.
A similar effect takes place for multipliers. For example, a “standard” multiplier implemented in the form of a Wallace tree with a final adder can be reduced to single Wallace tree, reducing the delay by about 30%. However, this faster multiplier will require approximately four times as many logic gates as the standard multiplier. Since a given multiplier already contains a high gate count, this faster multiplier is usually unacceptable.
Most integer arithmetic units employ redundant number representations.
The algebraic value of an N-bit redundant number [Xn−1, Xn−2, . . . X1, X0] (where Xiε{−1, 0, 1}) is equal to
      ∑          i      =      0              x      -      1        ⁢            X      i        *                  2        i            .      Redundant numbers are quite useful in adders (and subtractors) because of the property of performing additions without carry propagation. They are also useful in multipliers (and dividers) because redundant numbers do not require 2's complement methods to handle negative numbers. However, integer arithmetic units operate in what is referred to herein as a 1-redundant number system. Thus, the prior double-size adder designs and the multipliers employed 1-redundant concepts.
The present invention is directed to sparce-redundant arithmetic units that provide faster fixed-point arithmetic operations without significantly increasing the hardware implementation.